#ifndef LINEAR_LIST_H_
#define LINEAR_LIST_H_

#include <iostream>
using namespace std;

inline int MAX(x, y) { return (x > y ? x:y); }
inline int MIN(x, y) { return (x < y ? x:y); }

template <class T>
inline void change_capacity(T* &a, int old_len, int new_len)
{
	if (new_len < 0)
		throw illegalParameterValue("new length must be >= 0");
	
	T* temp = new T[new_len];
	int num = MIN(old_len, new_len);
	copy(a, a + num, temp);
	delete [] a;
	a = temp;
}


template<class T>
class LinearList{
public:
    virtual ~LinearList() {}
	virtual bool is_empty() const = 0;
	virtual int size() const = 0;
	virtual T& get(int index) const = 0;
	virtual int index(const T &element) const = 0;
	virtual void erase(int index) = 0;
	virtual void insert(int index, const T &element) = 0;
	virtual void output(ostream& out) const = 0;
	virtual ostream& operator<< (ostream &os, const T &element) const = 0;
};


template<class T>
class ArrayList: public LinearList {
public:
    ArrayList(int capacity = 10);
	ArrayList(const ArrayList<T>& );
	~ArrayList() { delete [] _element; }
	
	// iterators to start and end of list
	class iterator;
	iterator begin() {return iterator(_element); }
	iterator end()   {return iterator(_element + _size); }
	
	// iterator for arrayList
    class iterator 
    {
       public:
          // typedefs required by C++ for a bidirectional iterator
          typedef bidirectional_iterator_tag iterator_category;
          typedef T value_type;
          typedef ptrdiff_t difference_type;
          typedef T* pointer;
          typedef T& reference;

          // constructor
          iterator(T* thePosition = 0) {position = thePosition;}

          // dereferencing operators
          T& operator*() const {return *position;}
          T* operator->() const {return &*position;}

          // increment
          iterator& operator++()   // preincrement
                    {++position; return *this;}
          iterator operator++(int) // postincrement
          	      {iterator old = *this;
          	       ++position;
          	       return old;
          	      }

          // decrement
          iterator& operator--()   // predecrement
                    {--position; return *this;}
          iterator operator--(int) // postdecrement
          	      {iterator old = *this;
          	       --position;
          	       return old;
          	      }

          // equality testing
          bool operator!=(const iterator right) const
                {return position != right.position;}
          bool operator==(const iterator right) const
                {return position == right.position;}
       protected:
          T* position;
    };  // end of iterator class
	
	bool is_empty()   const { return _size == 0; }
    int size()        const { return _size; }
    T& get(int index) const;
	
    int  index(const T &element) const;
    void erase(int index);
    void insert(int index, const T &element);
    void output(ostream &out) const;
    ostream& operator<< (ostream &os, const T &element) const;
	
    int capacity() const { return _capacity; }

private:	
    void check_index(int index) const;
	
	T* _element;
	int const _init_capacity = 10;
	int _capacity;  
	int _size;
};


template<class T>
ArrayList<T>::ArrayList(int capacity)
{
	if (capacity < 1) {
		ostringstream s;
		s << "Initial capacity = " << capacity << " must be > 0";
		throw illegalParameterValue(s.str());
	}
	
	_capacity = capacity;
	_element = new T[_capacity];
	_size = 0;
}

template<class T>
ArrayList<T>::ArrayList(const ArrayList<T>& list)
{
	_capacity = list._capacity;
	_size = list._size;
	_element = new T[_capacity];
	copy(list._element, list._element + _size, _element);
}

template<class T>
inline void ArrayList<T>::
check_index(int index)
{
	if (index < 0 || index >= _size) {
		ostringstream s;
		s << "index = " << index << " size = " << _size;
		throw illegalIndex(s.str());
	}
}

template<class T>
inline T& ArrayList<T>::
get(int index) const
{
	check_index(index);
	return _element[index];
}

template<class T>
inline int ArrayList<T>::
index(T &element)
{
	int index = (int)(find(_element, _element + _size, element) - _element);
	
	if (index == _size)
		return -1;
	else 
		return index;
}

template<class T>
inline void ArrayList<T>::
erase(int index)
{
	check_index(index);
	copy(_element + index + 1, _element + _size, _element + index);
	_element[--_size].~T;
	
	if (_size < (_capacity/4)) {
		change_capacity(_element, _capacity, MAX(_capacity/4, _init_capacity));
	}
}

template<class T>
inline void insert(int index, const T &element)
{
	if (index < 0 || index > _size) {
		ostringstream s;
		s << "index = " << index << " size = " << _size;
		throw illegalIndex(s.str());
	}
	
	if (_size == index) {
		// array is full
		change_capacity(_element, _capacity, _capacity * 2);
		_capacity *= 2;
	}
	
	copy_backward(_element + index, _element + _size, _element + _size + 1);
	_element[index] = element;
}

template<class T>
inline void ArrayList<T>::
output(ostream &os = cout)
{
	copy(_element, _element + _size, ostream_iterator<T>(os, " "));
}

template<class T>
inline ostream& ArrayList<T>::
operator<< (ostream &os, const T &element)
{
	element.output(os);
	return os;
}

#endif